%!TEX root = main.tex


%\begin{figure}[t]
%    \centering
%        \includegraphics[width=0.5\textwidth]{pics/inverted_list}
%    \caption{inverted list design}
%    \label{fig:InvertedIndex}
%\end{figure}

\begin{figure}[t]
\vspace{-6mm}
\includegraphics[width=0.5\textwidth]{pics/balanced_3D_index}
\caption{3D inverted index for \quotes{icde}}
\label{fig:text_3D_inverted}
\end{figure}

\section{Index Design}\label{sec:Index}


To support fast-update for \textbf{highly dynamic} SNPs, we propose a 3D inverted index where time is the primary dimension. Textual and social dimensions
are also included to support efficient pruning.
Before introducing the 3D index design, we would like to present how to handle the social dimension first as it is not straightforward to order the records according to the social relevance without knowing who the query user is. 


\noindent{\bf Graph Partition}. Given a social graph $G$ like Fig. \ref{fig:social_graph}, we first divide the vertices into $c$ partitions using k-way partition \cite{Kway:Karypis:PMK:1996} with minimum cut utility. For each $P_i$, a pivot vertex $pn_i$ will be selected among the vertices in $P_i$ and the shortest distance from $pn_i$ to all vertices in $G$ will be pre-computed. In addition, for any two partitions $ P_i,P_j$, we pre-compute $\textbf{SD}(P_i,P_j) = \min_{x \in P_i, y \in P_j}{\textbf{SD}(x,y)}$. This index will be used for estimating the social distance between the query user $q.v$ and a partition. As the partitions along the social dimension do not have an ordering which depends on the query, we rank $P_i$ by $\textbf{SD}(P_{q.v},P_i)$ in query time where $P_{q.v}$ contains $q.v$. The space complexity of the index for social distance is $O(N+c^2)$ where $N$ is the number of vertices in the social graph.

\noindent {\bf 3D Inverted Index}. Each keyword $w$ is associated with a 3D list of records which contain $w$. Continuing our Example~\ref{exmp:rankmodel}, Fig.~\ref{fig:text_3D_inverted} shows the 3D list for keyword \quotes{icde}. The primary axis of the 3D list is time, from latest to oldest, which will be divided into slices. Each time slice contains a 2D grid consisting of the social and textual dimensions. The social dimension corresponds to the $c$ partitions constructed on $G$. The textual dimension is discretized to $m$ intervals w.r.t. the keyword frequencies $tf$. \reminder{how to discretize?}This results in a cube structure of the 3D list where each cube may contain 0 or many records. Note that in Fig.~\ref{fig:text_3D_inverted}, the time and textual dimensions are sorted offline whereas the social partitions will only be sorted against user $u_1$ when $u_1$ issues a query at runtime
as we have illustrated in Example~\ref{exmp:rankmodel}.

To support efficient retrieval of records from the 3D list (as discussed later in Sec. \ref{sec:qp}), we define the neighbours of a cube:
\begin{defn}
We assign each cube with a 3D number $(x,y,z)$, where $x,y,z$ refer to time, social and textual dimensions.  The 3 neighbours of cube $cb(x,y,z)$ are $cb(x-1,y,z)$, $cb(x,y-1,z)$, $cb(x,y,z-1)$ respectively.
\end{defn}
\vspace{-1mm}

\noindent For example in Fig.~\ref{fig:text_3D_inverted}, there are 18 cubes and the dimension indices (x,y,z) are listed in the first row of a cube. The cube $cb(1,1,1)$ which contains $r11$ have neighbours: $cb(0,1,1)$, $cb(1,0,1)$, $cb(1,1,0)$ along the time, social and textual dimensions respectively. To avoid storing empty cubes in the 3D list, we deploy a B$^+$-tree for each time slice as shown in Fig. \ref{fig:text_3D_inverted}. In each B$^+$-tree, the value of a leaf node represents a cube's linearized dimension index in the 2D grid. Suppose a cube has a grid index entry $(y,z)$ where $y$ and $z$ represent the entries of
the social and
textual dimensions respectively, then a leaf node with value $ym + z$ will be added to the B$^+$-tree. To facilitate random access, each B$^+$-tree will keep a reference to the leaf node with index $(y,\max{(z)})$ for each partition $y$.

\vspace{1mm}
\noindent {\bf Index Update}. When a new record $r$ arrives, it will be inserted into $w$'s 3D list $\forall w \in r.W$. $r$ will always be allocated to the latest time slice and mapped to the corresponding cube. When the number of records in the latest time slice exceeds a system determined threshold, a new time slice will be created. Let us take $r6$ for an example and assume the time slice threshold is 6. When $r6$ arrives, slice $1$ will be created as there are 6 records in slice $0$ and $r6$ will be inserted into slice $1$. Since $r6$ belongs to user $u_4$, $r6$ should go to partition $1$. Next, \quotes{icde} has a keyword frequency of $0.8$ in $r6$, which falls in the frequency interval $[1,0.7)$. Finally, $r6$ should be inserted into the cube $cb(1,0,2)$ that maps to leaf node $2$ after linearization. The B$^+$-tree will be updated accordingly.

\noindent {\bf Complexity}. Since the record is inserted into B+tree and each B+tree has at most $c\cdot m$ leaf nodes, the complexity of inserting a new record is just $O(|r.W|\cdot log(c\cdot m))$.

\noindent {\bf Forward Index}. To enable efficient random access, a forward list is built for each record $r$. Each list stores the keywords in $r$ and their keyword frequencies. The user who posts it and the time posted are stored as well. The table in Fig. \ref{fig:social_graph} is an example of the forward lists for the social network.

%The framework of the inverted list is shown in Fig. \ref{fig:InvertedIndex}. Each keyword $w$ is associated with a list of records where each record contains $w$. The key difference with common IR approach is, instead of sorting the documents by term frequency, our inverted list is constructed as 3D lists. Each dimension is bounded by $(0,1]$ after normalization.



%The number of documents per time slice, the graph partition size and the text frequency interval will be controlled by the administrator given the system requirements, i.e. memory size. Each of the small cubes in the 3D lists contains record information $(r.id,tf_{w,r})$. $r.id$ is the ID of this document and we have explained $tf_{w,r}$ in Equation $\ref{eq:TermFrequency}$. All 3D lists are divided into a memory resident part and a number of disk resident parts chopped by time dimension as it is impossible to store all the inverted lists in memory for real world scenario. The design purpose is to support efficient pruning without affecting fast updates since we are dealing with real time document search.
%\begin{figure}[h]
%    \centering
%        \includegraphics[width=0.5\textwidth]{pics/3Dinverted_index}
%    \caption{Example of inverted list for \quotes{vldb}}
%    \label{fig:text_3D_inverted}
%\end{figure}





%The social distance between any pair of users is the shortest distance in the graph. As described in Section \ref{sec:Introduction}, none of the existing work can be applied for the real time personalized query. Thus it motivates us to develop a series of pruning solutions to answer distance queries efficiently which we will illustrate in Section \ref{sec:ShortestPath}. To support such pruning solutions, we keep essential information for all partitions $P_i$s of the social graph. For each $P_i$, a pivot node $pn_i$ will be selected among the nodes in $P_i$ and the shortest distance from $pn_i$ to all nodes in $G$ will be pre-computed. In addition, $\forall P_i,P_j$, we pre-compute $\textbf{SD}(P_i,P_j) = \min_{x \in P_i, y \in P_j}{\textbf{SD}(x,y)}$. This index will be used for estimating the social distance between the query user and a partition. The space complexity of the index for social distance is $O(N)$ where $N$ is the number nodes in the social graph.
